A number theoretic transform is similar to a fast Fourier transform, but instead of using complex roots of unity, roots of unity modulo $n$ are used. This allows computing convolutions where arithmetic is taken modulo $n$, and thus avoids using floating point numbers as is the case for fast Fourier transform.

Problems

• Counting tuples

See also

• Fast Fourier transform
• Divide and conquer

External links

• Number theoretic transforms
• A week that ends with FFT
• Fast convolution for 64-bit integers